//
// Description: 452. 用最少数量的箭引爆气球
// Created by Loading on 2025/4/16.
//

#include <bits/stdc++.h>

using namespace std;

int findMinArrowShots(vector<vector<int>> &points) {
    if (points.size() == 1) {
        return 1;
    }
    // 仅按照右边界排序即可
    sort(points.begin(), points.end(), [](const vector<int> &v1, const vector<int> &v2) {
        return v1[1] < v2[1];
    });

    int res = 1;
    int end = points[0][1]; // 可以引爆的气球的最小右边界
    for (const auto &v : points) {
        if (v[0] > end) { // 完成一支射箭
            ++res;
            end = v[1];
        }
    }

    return res;
}

int main() {
    vector<vector<int>> points{{10, 16},
                               {2,  8},
                               {1,  6},
                               {7,  12}};

    auto res = findMinArrowShots(points);

    cout << res << endl;

    return 0;
}
